A fundamental problem in communication theory is how to transmit a message, M, between two parties without a third party also being able to obtain the message. For example, in the field of electronic financial transactions, it is very important to maintain secrecy in the communication between two parties.
Conventionally, the two parties who wish to exchange a message are known respectively as Alice and Bob, while an eavesdropper who wishes to gain unauthorised access to the message M is known as Eve.
Many communication techniques have been developed to solve this problem. One class of techniques relies on the computational limitations of Eve that prevent her from performing certain mathematical operations in a reasonable time. For example the security of the RSA public key cryptographic technique relies heavily on the computational difficulty in factoring very large integers. Techniques of this type are known as “conditionally secure” or “computationally secure”.
One problem with conditionally secure techniques is that confidence in their security relies on mathematical results in the field of complexity theory that remain unproven. Therefore, it cannot, at present, be certain that such techniques will not be broken in the future, using only the resources of a classical computer, if appropriate mathematical tools for doing so can be developed. Furthermore, the development of quantum computational techniques renders conditionally secure techniques vulnerable due to the potential ability of quantum computers to perform certain mathematical operations, including operations on which computationally secure techniques rely, much faster than a classical computer.
Therefore, there has been a great deal of interest in the development of a class of communication techniques that makes no assumptions about the computing power of Eve. Techniques of this type are known as “unconditionally secure”.
One example of an unconditionally secure data transmission scheme is known as the “one-time pad”. According to this technique, Alice bitwise modulo-2 adds (i.e. XORs) a binary plaintext string (the message M) and a secret random binary string (the one-time pad) having the same length as the message. The resulting binary ciphertext string (the enciphered message Mε) is transmitted to Bob instead of the original message M. To recover the original message M, Bob bitwise modulo-2 adds a local copy of the one-time pad to the received enciphered message Mε. Even if Eve intercepts the transmitted enciphered message Mε, it is impossible for Eve to recover the original message M without knowledge of the one-time pad. As suggested by the name, the one-time pad is used only once to help preserve security.
A fundamental requirement of any secure communication scheme is that Alice and/or Bob must possess some kind of secret information that is unknown to Eve. This secret information is used as the basis of the encryption and/or subsequent decryption of a message. In some schemes, it is necessary for both Alice and Bob to possess at least some secret information that is at least partially shared between them. For example, the secret information may be in the form of the random binary string in the one-time pad scheme described above. In this case, the secret information is fully shared between Alice and Bob.
One problem with any secure communication technique requiring shared secret information is how to distribute the secret information between Alice and Bob without it becoming known to Eve. This problem can be especially acute in the case of techniques such as the one-time pad, in which the amount of secret information required is comparable to the amount of plaintext message data. Therefore, what is desired is a technique that allows Alice and Bob to obtain shared secret information, and in particular, to obtain this information in an unconditionally secure manner.
As described above, shared secret information is first distributed between Alice and Bob using a first mechanism, and then Alice and Bob use a second mechanism involving the shared secret information to exchange a message. One reason why this two-stage approach is used, rather than to simply directly exchange the message using the first mechanism, is that mechanisms suitable for allowing Alice and Bob to obtain shared secret information without prior shared information may be unsuitable or impractical for message exchange in some cases. For example, some mechanisms allow Alice and Bob to obtain shared secret information, but do not allow Alice and Bob to control the exact content of the shared secret information.